Achieving such guarantees generally requires the injection of noise, either directly into parameter estimates or into the estimation process.

We resolve a 30-year-old open problem concerning the power of unlabeled data in online learning by tightly quantifying the gap between transductive and standard online learning. In the standard setting, the optimal mistake bound is characterized by the Littlestone dimension $d$ of the concept class $H$ (Littlestone 1987). We prove that in the transductive setting, the mistake bound is at least $Ω(\sqrt{d})$. This constitutes an exponential improvement over previous lower bounds of $Ω(\log\log d)$, $Ω(\sqrt{\log d})$, and $Ω(\log d)$, due respectively to Ben-David, Kushilevitz, and Mansour (1995, 1997) and Hanneke, Moran, and Shafer (2023). We also show that this lower bound is tight: for every $d$, there exists a class of Littlestone dimension $d$ with transductive mistake bound $O(\sqrt{d})$. Our upper bound also improves upon the best known upper bound of $(2/3)d$ from Ben-David, Kushilevitz, and Mansour (1997). These results establish a quadratic gap between transductive and standard online learning, thereby highlighting the benefit of advance access to the unlabeled instance sequence. This contrasts with the PAC setting, where transductive and standard learning exhibit similar sample complexities.

Conditional probabilities are a core concept in machine learning.

This paper proposes REFUEL, a reinforcement learning method with two techniques: reward shaping and feature rebuilding, to improve the performance of online symptom checking for disease diagnosis.

Next, we develop algorithms for performing HSC (which we refer to as "inference rules"), and propose an efficient algorithm that guarantees a target accuracy

The code is available here.

Decentralized air tra ffic management systems o ff er a scalable alternative to centralized control, but often assume high levels of cooperation. In practice, such assumptions frequently break down since airspace sectors operate independently and prioritize local objectives. We address the problem of sector overload in decentralized air tra ffic management by proposing a mechanism that models self-interested behaviors based on best response dynamics. Each sector adjusts the departure times of flights under its control to reduce its own congestion, without any shared decision making. A tunable cooperativeness factor models the degree to which each sector is willing to reduce overload in other sectors. We prove that the proposed mechanism satisfies a potential game structure, ensuring that best response dynamics converge to a pure Nash equilibrium, under a mild restriction. In addition, we identify a su fficient condition under which an overload-free solution corresponds to a global minimizer of the potential function. Numerical experiments using 24 hours of European flight data demonstrate that the proposed algorithm substantially reduces overload even with only minimal cooperation between sectors, while maintaining scalability and matching the solution quality of centralized solvers. Keywords: Air Tra ffi c Management, Noncooperative Coordination, Game Theory, Potential Game, Decentralized System, Sector Overload 1. Introduction Decentralized approaches to air tra ffic management (A TM) are gaining attention as scalable alternatives to centralized control [1, 2, 3, 4, 5], due to the increasing complexity of air tra ffic.